package com.javabasic.algorithm.sword_of_offer;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/1/16 3:31 下午
 */
public class 剑指_Offer_52_两个链表的第一个公共节点 {

    /**
     * 两个交替走，走到链表A加链表B的长度时，如果有交点这当前指针指向必定相同，如果不同这这两链表必不有交点
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode preHeadA = new ListNode(-1);
        ListNode preHeadB = new ListNode(-1);
        preHeadA.next = headA;
        preHeadB.next = headB;

        int nullTimes = 0;
        while (true) {
            /**
             * 确定A链表往下走的下一个节点位置
             */
            if (preHeadA.next == null) {
                nullTimes++;
                if (nullTimes > 1) {
                    return null;
                }
                preHeadA = headB;
            } else {
                preHeadA = preHeadA.next;
            }

            /**
             * 确定B链表往下走的下一个节点位置
             */
            if (preHeadB.next == null) {
                preHeadB = headA;
            } else {
                preHeadB = preHeadB.next;
            }
            if (preHeadA == preHeadB) {
                return preHeadA;
            }
        }
    }
}
